/*
题目：平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

    一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
https://leetcode.cn/problems/balanced-binary-tree/
 */
public class IsBalanced {
    //O(n)，在求高度的时候判断是否满足题意
    private int height(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1) {
            return Math.max(leftHeight,rightHeight) + 1;
        }
        return -1;
    }
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;

        return height(root) != -1;
    }
}

class IsBalancedd {
    //O(n²)
    private int height(TreeNode root) {
        if (root == null) return 0;
        return Math.max(height(root.left), height(root.right)) + 1;
    }
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        int leftHeight = height(root.left);//左边的高度
        int rightHeight = height(root.right);//右边的高度
        return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
}